#include<string>
#include<vector>
using namespace std;
class WordDictionary {
private:
    bool isEnd;
    WordDictionary* next[26];
public:
    /** Initialize your data structure here. */
    WordDictionary() {
        isEnd = false;
        memset(next, 0, sizeof(next));
    }

    /** Adds a word into the data structure. */
    void addWord(string word) {
        WordDictionary* p = this;
        for (int i = 0; i < word.size(); ++i) {
            if (p->next[word[i] - 'a'] == nullptr) {
                p->next[word[i] - 'a'] = new WordDictionary();
            }
            p = p->next[word[i] - 'a'];
        }
        p->isEnd = true;
    }

    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    bool search(string word) {
        if (word.size() == 0) return isEnd;
        WordDictionary* node = this;
        if (word[0] == '.') {
            for (int i = 0; i < 26; ++i) {
                if (node->next[i] != nullptr && node->next[i]->search(word.substr(1,word.size()-1)))
                    return true;
            }
        }
        else if(node->next[word[0] - 'a'] != nullptr)
            return  node->next[word[0] - 'a']->search(word.substr(1, word.size() - 1));
        return false;
    }
};

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary* obj = new WordDictionary();
 * obj->addWord(word);
 * bool param_2 = obj->search(word);
 */